// 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/contains-duplicate-ii
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;

// hash

class Solution
{
private:
    /* data */
public:
    bool containsNearbyDuplicate(vector<int>& nums,int k){
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();++i){
            if(hash.count(nums[i])){
                if((i-hash[nums[i]])<=k){
                    return true;
                }
                else{
                    hash[nums[i]] = i;
                }
            }
            else{
                hash[nums[i]]=i;
            }
        }
        return false;
    }

};



int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> nums={1,2,3,1};
    int k=3;
    Solution s;
    cout<<s.containsNearbyDuplicate(nums,k)<<endl;
    return 0;
}
